# 654.最大二叉树
# 给定一个不重复的整数数组nums 。 最大二叉树可以用下面的算法从nums递归地构建:
# 创建一个根节点，其值为nums中的最大值。
# 递归地在最大值左边的子数组前缀上构建左子树。
# 递归地在最大值右边的子数组后缀上构建右子树。
# 返回nums构建的最大二叉树 。
#
# 示例1：
# 输入：nums = [3, 2, 1, 6, 0, 5]
# 输出：[6, 3, 5, null, 2, 0, null, null, 1]
# 解释：递归调用如下所示：
# - [3, 2, 1, 6, 0, 5]中的最大值是6 ，左边部分是[3, 2, 1] ，右边部分是[0, 5] 。
# - [3, 2, 1]中的最大值是3 ，左边部分是[] ，右边部分是[2, 1] 。
# - 空数组，无子节点。
# - [2, 1]中的最大值是2 ，左边部分是[] ，右边部分是[1] 。
# - 空数组，无子节点。
# - 只有一个元素，所以子节点是一个值为1的节点。
# - [0, 5]中的最大值是5 ，左边部分是[0] ，右边部分是[] 。
# - 只有一个元素，所以子节点是一个值为0的节点。
# - 空数组，无子节点。
#
# 示例2：
#
# 输入：nums = [3, 2, 1]
# 输出：[3, null, 2, null, 1]


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: [int]) -> [TreeNode]:
        # 和106.105一样的写法，甚至还要简单一点，构造一个二叉树就可以
        # 写完才发现自己写的是前序遍历
        def traver(nums)->TreeNode:
            if not nums:
                return None
            root_val = max(nums)
            root = TreeNode(root_val)
            # 叶子节点就返回  ——这里为什么可以删除
            # if len(nums) == 1:
            #     return root
            d_index = nums.index(root_val)
            # 构造左子树
            left_nums = nums[:d_index]
            # 构造右子树，+1是为了略过根值
            right_nums = nums[d_index+1:]
            root.left = traver(left_nums)
            root.right = traver(right_nums)
            return root
        if not nums:
            return None
        return traver(nums)
if __name__ == '__main__':
    nums = [3, 2, 1]
    nums = [3, 2, 1, 6, 0, 5]
    tmp = Solution()
    res =tmp.constructMaximumBinaryTree(nums)
    print(res)

